Shared Risk Link Group (SRLG) has been widely recognized as an important concept in survivable optical networks by the industry. Both standardization documents and commercial products are incorporating SRLG-aware components. However, SRLG-related problems of theoretical interest have only recently attracted the attention of the research community, and some of them have not been explored fully. More specifically, there are two major issues that are still open: avoiding “traps” (to be defined later) in path determination, and maximizing bandwidth sharing. These issues are more challenging in providing shared SRLG protection than in providing shared path protection without considering SRLGs.
Dense Wavelength Division Multiplexing (DWDM) is a promising technology to accommodate the explosive growth of Internet and telecommunication traffic. Because of the large amount of traffic a fiber carries, a single failure may cause a severe service loss. Hence, survivability is a critical problem in network design. To protect a mission-critical connection from a single link (node) failure, a straightforward solution is to choose a link (node) disjoint pair of active path (or AP, also called working path or primary path) and backup path (or BP, also called secondary path) from a source (ingress) node to a destination (egress) node. Such a scheme is failure-independent and this scheme can realize fast restoration by eliminating route computation in case of failure. In addition, bandwidth usage efficiency can be improved by using shared path protection, which allows a new BP to share the bandwidth allocated to some existing BPs on common links if their APs do not fail at the same time.
The concept of Shared Risk Link Group (SRLG) has been proposed as the fundamental input for failure management in the Generalized Multi-Protocol Label Switching (GMPLS) control plane. An SRLG is a group of network links that share a common physical resource (cable, conduit, node or substructure) whose failure will cause the failure of all links of the group. In general, the information on SRLGs are obtained manually by the network operator with the knowledge of the physical fiber plant of the network, although some SRLGs auto-discovery schemes have been proposed.
SRLG is an important component in survivable network design. In order to provide the failure-independent protection to a client (e.g., IP, ATM) connection from any single SRLG failure, a pair of SRLG-disjoint paths (AP and BP) for each client connection should be determined. That is, links allowing AP must not share any common SRLGs with links along the corresponding BP.
FIG. 1(a) illustrates an optical layer of an optical network. In general, an optical network has a layered architecture. In the following discussion, a typical optical network is classified into two layers: an optical layer and a physical layer, as shown in FIG. 1a. The physical layer includes fiber spans (e.g., cable, conduit, etc.) and fiber span nodes. And the optical layer consists of optical links and nodes (a subset of the nodes in the physical layer) where Optical Cross-connects (OXC) or Optical Add/Drop Multiplexer (OADM) locate. An optical link in the optical layer is a connection in the physical layer, which may traverse over several fiber spans and/or fiber span nodes. At the same time, several optical links may pass through the same fiber span. Therefore, a single failure in the physical layer can cause multiple optical link failures. If we treat each fiber span as an SRLG, then a single SRLG failure may result in multiple optical link failures.
Since a fiber can traverse several conduits, a network link may belong to several SRLGs. Finding a pair of SRLG disjoint paths will be more complicated than finding a link/node-disjoint path (the latter may be considered as a special case as each link or the set of links incident upon each node could be what we call a “trivial SRLG”). In fact, the former is an NP-complete problem, while the later has a polynomial time solution.
To date, only a few Integer Linear Programming (ILP) and heuristic algorithms have been proposed to find SRLG disjoint paths. In shared SRLG failure-independent protection, or shared SRLG protection for short, the objective is to find a pair of SRLG-disjoint paths for a given request such that the total bandwidth consumption is minimized, taking into consideration that the two or more BPs can share backup bandwidth (called BBW) as long as their corresponding APs do not fail at the same time. In addition, the problem of online shared SRLG protection also need to be considered.
As expected, an ILP-based solution to the shared SRLG protection problem is extremely time-consuming and becomes infeasible for a large network size and/or a large number of SRLGs. Accordingly, heuristics such as Active Path First (APF), which finds an AP first, followed by a SRLG-disjoint BP, are attractive alternatives. The major challenge in using the APF heuristic, however, is that once an AP is found, one may not be able to find an SRLG-disjoint BP (even though a pair of SRLG-disjoint paths does exist). This is the so-called trap problem, which is rarely present when finding link/node-disjoint paths using APF, but can occur much more frequently (e.g., 10% to 30% in a typical network) when finding SRLG-disjoint paths using APF. To our knowledge, no effective algorithms have been proposed so far to address the trap problem, especially in conjunction with shared SRLG protection.
What is needed, then, is a fast and efficient heuristic algorithm for avoiding traps, an algorithm which may also be applied effectively to shared SRLG protection. This patent addresses issues related to both shared protection and trap avoidance jointly in survivable networks with SRLG consideration. Compared to other existing algorithms, the algorithm embodied in the present invention runs much faster, and yet falls into few traps, and achieves a much higher bandwidth efficiency. This technology can be applied to MPLS, ATM, SONET, WDM, and other high-speed survivable network designs.